package list;

public class ListToTree {
    public static void main(String[] args) {
        Node head = new Node(1, null, new Node(3, null, new Node(5, null, new Node(7, null, null))));
    }

    public static Node buildBSTfromList(Node head){
        int countOfNodes = countNodes(head);
        return buildBSTfromList(head, countOfNodes);
    }

    private static Node buildBSTfromList(Node head, int countOfNodes) {
        if(countOfNodes<=0) return null;
        Node left = buildBSTfromList(head, countOfNodes/2);
        head.prev=left;
        head = head.next;
        head.next=buildBSTfromList(head,countOfNodes/2);
        return head;
    }

    private static int countNodes(Node head) {
        if(head==null) return 0;
        Node current = head;
        int counter=1;
        while(current.next!=null){
            current=current.next;
            counter++;
        }
        return counter;
    }

    private static class Node {
        int data;
        Node prev, next;

        private Node(int data) {
            this.data = data;
        }

        private Node(int data, Node prev, Node right) {
            this.data = data;
            this.prev = prev;
            this.next = right;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", prev=" + prev +
                    ", next=" + next +
                    '}';
        }
    }
}
